#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class NumberCombine:
    def __init__(self, target_num=-1):
        self.num = target_num
        self.memory = {}            # dp的记忆体, 空间换时间, 递归中已经计算过的子问题做记录

        self.hit_memory_cnt = 0

    def partion_cnt(self):
        if self.num == 0:
            return 1

        cnt = 0
        for part_n in range(1, self.num+1):
            cnt += self.partion_cnt_part_n(self.num, part_n)

        return cnt

    def partion_cnt_part_n(self, num, part_n):
        return self.partion_cnt_rec_n_with_min(num, part_n, min_value=1)

    def partion_cnt_rec_n_with_min(self, num, part_n, min_value, depth=0):
        # 将num分割成part_n份, 最小值是min_value
        key = num, part_n, min_value
        res = self.memory.get(key)
        if res is not None:
            return res

        assert num != 0
        assert part_n != 0
        assert min_value != 0

        if num == part_n:
            # print('hit equal')
            cnt = 1

        elif 1 == part_n:
            # print('hit 1')
            cnt = 1

        # 分情况讨论分成part_n份
        else:
            cnt = self.split(num, part_n, min_value, depth)
            self.memory[key] = cnt

        print(depth*"    ", key, cnt)
        return cnt

    def split(self, num, part_n, min_value, depth):
        # 分情况讨论分成part_n份
        assert num > part_n

        cnt = 0
        # 如果num分成part_n份, 那么最大的数是num - (part_n-1): 其它part_n-1个数最小, 都是1, 剩下一个数最大
        # remain = num - (part_n-1)
        big_min = num // part_n

        for min_num in range(min_value, big_min+1):
            # 分成part_n份, 第一个数的可能性first_num
            # 但是注意这其中包含了所有的可能的(重复的)情况:
            # 比如(5, 2): 5个数分成两个数, 第一个数是3, 那么剩下只能是2
            # 如果第一个数是2, 那么剩下只能是3(这两种情况, 相当于同构)
            cnt += self.partion_cnt_rec_n_with_min(num-min_num, part_n-1, min_num, depth+1)


        return cnt


def test():
    ans_lst = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604]

    # for num, cnt in enumerate(ans_lst):
    #     n = NumberCombine(num)
    #     assert n.partion_cnt() == cnt

    # n = NumberCombine()
    # assert n.partion_cnt_part_n(15, 7) == 21      # 将15分成7份, 有多少种不同构的可能性?

    # n = NumberCombine()
    # assert n.partion_cnt_rec_n_with_min(15, 7, 1) == 21     # 将15分成7份, 最小值为1, 有多少种不同构的可能性?

    # n = NumberCombine()
    # assert n.partion_cnt_rec_n_with_min(15, 7, 2) == 1      # 将15分成7份, 最小值为2, 有多少种不同构的可能性?

    # n = NumberCombine()
    # assert n.partion_cnt_rec_n_with_min(15, 7, 3) == 0      # 将15分成7份, 最小值为3, 有多少种不同构的可能性?

    n = NumberCombine()
    assert n.partion_cnt_part_n(10, 5)  == 7



def main():
    print("start main")
    test()


if __name__ == "__main__":
    main()
